//
// 单链表实现链式队列。Created by Bianwy on 2024/2/8.
//
#include <iostream>

using namespace std;

// 链队数据结点类型
template <typename T>
struct LinkNode
{
    T data;     // 结点数据域
    LinkNode *next; // 指向下一个结点
    // 构造函数
    LinkNode():next(nullptr) {}
    LinkNode(T d):data(d), next(nullptr) {}
};
// 链队列类模板
template <typename T>
class LinkQueue
{
private:
    LinkNode<T>* front; // 队头指针
    LinkNode<T>* rear;  // 队尾指针
public:
    // 队列的基本运算算法
    // 链队列的初始化和销毁
    LinkQueue() // 构造函数
    {
        front = nullptr;    // 置为不带头结点的空单链表
        rear = nullptr;
    }
    ~LinkQueue()    // 析构函数
    {
        LinkNode<T>* pre = front, *p;
        if(pre != nullptr)  // 非空队列
        {
            if(pre == rear) // 只有一个结点的情况
                delete pre; // 释放pre结点
            else
            {
                p = pre->next;
                while(p!= nullptr)
                {
                    delete pre; // 释放pre结点
                    pre = p;
                    p = p->next;    // pre和p同步后移
                }
                delete pre; // 释放尾结点
            }
        }
    }
    // 判队为空运算
    bool empty()
    {
        return front == nullptr;    // 或 rear == nullptr
    }
    // 进队运算
    bool push(T e)
    {
        auto p = new LinkNode<T>(e);
        if(rear == nullptr) // 若链队为空
            front = rear = p;   // 新结点既是队首结点又是队尾结点
        else    // 若链队不空
        {
            rear->next = p; // 将p结点链到队尾，并将rear指向它
            rear = p;
        }
        return true;
    }
    // 出队运算
    bool pop(T& e)
    {
        if(rear == nullptr) // 队列为空
            return false;
        auto p = front; // p 指向首结点
        if(front == rear)   // 队中只有一个结点
            front = rear = nullptr;
        else        // 队列中有多个结点
            front = front->next;
        e = p->data;
        delete p;   // 释放出队结点
        return true;
    }
    // 取队头元素
    bool gethead(T& e)
    {
        if(rear == nullptr) // 队列为空
            return false;
        e = front->data;    // 取首结点的值
        return true;
    }
};